package com.fjl.code.jd;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
	ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class LinkedList {
    
    // 删除倒数第N个节点
    public static ListNode deleteNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头结点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 快慢指针初始化
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // 快指针先移动n步
        for (int i = 0; i <= n; i++) {
			if (fast==null&&i<=n){
				System.out.println("数据不合法");
				return null;
			}
            fast = fast.next;
        }
        
        // 快慢指针一起移动，直到快指针到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // 删除倒数第n个节点
        slow.next = slow.next.next;
        
        // 返回新的头结点
        return dummy.next;
    }
    
    // 打印链表
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 构造一个测试链表：1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(4);
//        head.next.next.next.next = new ListNode(5);

        System.out.println("Original List:");
        printList(head);
        
        // 删除倒数第2个节点
        head = deleteNthFromEnd(head, 2);

        System.out.println("List after deletion:");
        printList(head);
    }
}
